#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N=1e3+10;
const int M=1e4+10;
const int INF=0x3f3f3f3f;

int h[M],ne[M],to[M],w[M],idx;
int a[N];
int vis[N];
int dist[N];
int n,m;
struct cmp
{
	bool operator ()(const pair<int,int>& p1,const pair<int,int>& p2)
	{
		if(p1.second==p2.second)
			return p1.first<p2.first;
		return p1.second>p2.second;
	}
	
};
void add(int x,int y,int z)
{
	ne[idx]=h[x];
	to[idx]=y;
	w[idx]=z;
	h[x]=idx++;
}
void dijkstra()
{
	priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> q;
	q.push({1,0});
	while(q.size())
	{
		int u=q.top().first;
		int d=q.top().second;
		q.pop();
		if(vis[u])
			continue;
		vis[u]=1;
		for(int i=h[u];~i;i=ne[i])
		{
			int j=to[i];
			if(dist[j]>d+w[i]+a[u])
			{
				dist[j]=d+w[i];

				q.push({j,dist[j]});
			}
			
		}
	}
}
int main()
{
	
	cin>>n>>m;
	memset(h,-1,sizeof(h));
	memset(dist,INF,sizeof(dist));
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	
	a[1]=0;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	dist[1]=0;
	dijkstra();
	cout<<dist[n];
	return 0;
}
